package com.leetcode.partition2;

import java.util.*;

/**
 * @author `RKC`
 * @date 2021/9/13 18:24
 */
public class LC140单词拆分2 {

    public static List<String> wordBreak(String s, List<String> wordDict) {
        Map<Integer, List<List<String>>> memory = new HashMap<>();
        List<List<String>> result = memoization(s, 0, new HashSet<>(wordDict), memory);
        List<String> answer = new ArrayList<>();
        for (List<String> item : result) {
            answer.add(String.join(" ", item));
        }
        return answer;
    }

    public static void main(String[] args) {
//        String s = "catsanddog";
//        List<String> wordDict = Arrays.asList("cat", "cats", "and", "sand", "dog");
//        System.out.println(wordBreak(s, wordDict));
        System.out.println((int) '1');
    }

    private static List<List<String>> memoization(String str, int startIndex, Set<String> wordDict, Map<Integer, List<List<String>>> memory) {
        if (memory.containsKey(startIndex)) return memory.get(startIndex);
        List<List<String>> wordBreaks = new LinkedList<>();
        if (startIndex == str.length()) {
            wordBreaks.add(new ArrayList<>());
        }
        for (int i = startIndex + 1; i <= str.length(); i++) {
            String word = str.substring(startIndex, i);
            if (wordDict.contains(word)) {                //当前切割方式能在词典中找到单词
                List<List<String>> nextWordBreaks = memoization(str, i, wordDict, memory);       //将当前单词的后半部分继续递归截取
                for (List<String> nextWordBreak : nextWordBreaks) {
                    LinkedList<String> wordBreak = new LinkedList<>(nextWordBreak);             //将得到的子串的有效单词合并
                    wordBreak.offerFirst(word);           //当前切割的合法单词放入第一个
                    wordBreaks.add(new ArrayList<>(wordBreak));
                }
            }
        }
        memory.put(startIndex, wordBreaks);
        return memory.get(startIndex);
    }
}
